#ifndef SOLUTION_H_
#define SOLUTION_H_
#ifndef NULL
#define NULL 0
#endif
struct ListNode 
{
	int val;
	ListNode *next;
	ListNode(int x) : val(x), next(NULL) {}
};

class Solution 
{
public:
    ListNode *reverseKGroup(ListNode *head, int k)
	{
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        ListNode *pre = NULL, *h=head,*e,*behind;

		while(true)
		{
			e = h;
			for(int i=1;i<k;i++)
			{
				if(e)
					e=e->next;
				else
					break;
			}

			if(!e)
				break;

			reverse(pre,h,e,e->next);
		
			if(!pre)
			{
				head = e;
			}
			pre = h;
			h = pre->next;
		}

		return head;
    }

private:
	ListNode* reverse(ListNode* pre, ListNode* head, ListNode* end, ListNode* behind)
	{
		ListNode *tpre = pre, *tcur = head, *tend;
		while(tcur!=behind)
		{
			tend = tcur->next;
			tcur->next = tpre;
			tpre = tcur;
			tcur = tend;
		}

		head->next = behind;
		if(pre)
			pre->next = end;
		
		return head;	
	}
};
#endif
